#include <iostream>

template <typename T>
struct Allocator
{
    // 开辟内存
    T* allocate(const int size)
    {
        return (T*) malloc(sizeof(T) * size);
    }
    // 释放内存
    void deallocate(T* ptr)
    {
        free(ptr);
    }
    // 在指定位置拷贝构造一个对象
    void construct(T* ptr, const T& val)
    {
        new (ptr) T(val);
    }
    // 析构对象
    void destory(T* ptr)
    {
        ptr->~T();
    }
};


template <typename T, typename Alloc = Allocator<T>>
class MyVector
{
public:
    // 使用内置类实现容器的迭代器
    class Iterator
    {
    public:
        friend class MyVector<T, Alloc>;
        Iterator(MyVector<T, Alloc> *pvec = nullptr, T* p = nullptr)
            :_ptr(p)
            ,_pvec(pvec) 
        {
            Iterator_Base *iter_base = new Iterator_Base(this, _pvec->_head.next);
            _pvec->_head.next = iter_base;
        }
        void operator++() // 没有参数int是前置++, 后置++会产生临时对象
        {
            if(this->_pvec == nullptr)
            {
                throw "iterator is invalid...";
            }
            _ptr ++;
        }
        bool operator!=(const Iterator& src)
        {
            if(_pvec != src._pvec || _pvec == nullptr)
            {
                throw "iterator is invalid...";
            }
            return _ptr != src._ptr;
        }
        T& operator*()
        {
            if(this->_pvec == nullptr)
                throw "iterator is invalid...";
            return *_ptr;
            
        }
        bool operator==(const Iterator& src)
        {
            if(this->_pvec != src._pvec)
                throw "iterator is invalid...";
            return this->_ptr == src._ptr;
        }
    private:
        T* _ptr;
        MyVector<T, Alloc> *_pvec; // 创建一个指针指向当前容器，不同容器的指针不能进行比较，没有意义
    };
    
    // 存储迭代器的结构体
    struct Iterator_Base
    {
        Iterator_Base(Iterator* c = nullptr, Iterator_Base* n = nullptr) : cur(c), next(n) {}
        Iterator* cur; // 指向当前迭代器对象指针
        Iterator_Base* next; // 指向下一个迭代器结构体指针
    };
    MyVector(const int size = 10)
        :_head(nullptr, nullptr)
    {
        // 使用空间配置器开辟一块size大小的内存空间
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }
    // 析构函数
    ~MyVector()
    {
        // 释放掉内部空间中的有效元素
        T* tmp = _first;
        for(; tmp != _last; ++ tmp)
        {
            _allocator.destory(tmp);
        }
        _allocator.deallocate(_first);
        _first = _last = _end = nullptr;
        // 释放链表
        Iterator_Base pre = _head;
        Iterator_Base *it = _head.next;
        while(it != nullptr)
        {
            pre.next = it->next;
            delete it;
            it = pre.next;
        }
    }
    // 拷贝构造函数
    MyVector(const MyVector<T>& src)
    {
        // 类的成员方法中，同类型可以访问其私有成员变量
        _init(src, _first);
    }
    MyVector<T>& operator=(const MyVector<T>& src)
    {
        if(this == &src)
            return *this;
        // 先析构有效元素并删除内存
        T* tmp = _first;
        for(; tmp != _last; ++ tmp)
        {
            _allocator.destory(tmp);
        }
        _allocator.deallocate(_first);
        // 重新开辟内存并赋值
        _init(src, _first);
        return *this;
    }
    T& operator[](const int& index)
    {
        if(index < 0 || index >= size())
        {
            throw "out_of_range";
        }
        return _first[index];
    }
    void push_back(const T& val)
    {
        if(full())
            expand();
        // 在指定位置构造一个对象
        _allocator.construct(_last ++, val);
    }
    void pop_back(void) 
    {
        if(empty())
            return;
        // 从指定位置析构对象
        verify(_last - 1, _last);
        _allocator.destory(--_last);
    }
    const T& top(void) const
    {
        return *_last;
    }
    bool full() const { return _last == _end; }
    bool empty() const { return _last == _first; }
    int size() const { return _end - _first; }
    int length() const { return _last - _first; }
    Iterator begin() { return Iterator(this, _first); }
    Iterator end() { return Iterator(this, _last); }
    
private:
    T* _first;  // 向量容器的初始指针
    T* _last;   // 向量容器的有效元素最后指针的后继位置
    T* _end;    // 向量容器的容量的后继指针
    Alloc _allocator; // 空间配置器
    Iterator_Base _head; // 迭代器链表头节点
    void _init(const MyVector<T>& src, T* &entry)
    {
        int size = src._end - src._first;
        int len = src._last - src._first;
        entry = _allocator.allocate(size);
        for(int i = 0; i < len; i ++)
        {
            entry[i] = src._first[i];
        }
        _last = entry + len;
        _end = entry + size;
    }
    void expand()
    {
        // 扩容至原来的2倍大小
        int size = _end - _first;
        int len = _last - _first;
        T* tmp = _allocator.allocate(size * 2);
        // 删除有效元素和内存
        for(int i = 0; i < len; i ++)
        {
            _allocator.construct(tmp + i, _first[i]);
            _allocator.destory(_first + i);
        }
        _allocator.deallocate(_first);
        _first = tmp;
        _last = _first + len;
        _end = _first + size * 2;
    }
    
    void verify(T* start, T* finish)
    {
        // 遍历链表，如果有在start 和 finish指针范围内的节点 将节点中指向容器的指针置为nullptr，意味着迭代器失效了
        Iterator_Base pre = _head;
        Iterator_Base *it = _head.next;
        while (it != nullptr)
        {
            if(it->cur->_ptr >= start && it->cur->_ptr <= finish)
            {
                it->cur->_pvec = nullptr; // 将次迭代器置为失效迭代器
                pre.next = it->next;
                delete it;
                it = pre.next;
            }
            else
            {
                pre = *it;
                it = it->next;
            }
            
        }
        

    }
};

class Test
{
public:
    Test(int a):ma(a) {  }
    ~Test() {  }
private:
    int ma;
    friend std::ostream& operator<<(std::ostream& out, const Test& src);
};

std::ostream& operator<<(std::ostream& out, const Test& src)
{
    out << src.ma;
    return out;
}

int main(int argc, char const *argv[])
{
    MyVector<int> vec;
    vec.push_back(1);
    vec.push_back(1);
    vec.push_back(1);
    MyVector<int>::Iterator it1 = vec.end();
    vec.pop_back();
    MyVector<int>::Iterator it2 = vec.end();
    std::cout << (it1 == it2) << std::endl;
#if 0
    MyVector<Test> vec;
    for(int i = 0; i < 20; ++ i)
        vec.push_back(Test(rand() % 100));
    for(int i = 0; i < vec.length(); i ++)
        std::cout << vec[i] << std::endl;
    MyVector<Test> vec;
    for(int i = 0; i < 5; i ++)
    {
        vec.push_back(Test(rand() % 100));
    }

    MyVector<Test>::Iterator it = vec.begin();
    for(; it != vec.end(); ++ it)
        std::cout << *it << std::endl;
    
    for(Test& t : vec)
        std::cout << t << std::endl;
    


    MyVector<int> vec;
    for(int i = 0; i < 30; i ++)
    {
        vec.push_back(i + 1);
    }
    MyVector<int>::Iterator it = vec.begin();
    for(; it != vec.end(); ++it)
    {
        std::cout << *it << std::endl;
    }
    while(!vec.empty())
    {
        // std::cout << vec.top() << " ";
        std::cout << vec.top() << " ";
        vec.pop_back();
    }
    std::cout << std::endl;
#endif
    return 0;
}
